746. Min Cost Climbing Stairs

Easy

On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed).

Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.

Example 1:

Input: cost = [10, 15, 20]
Output: 15
Explanation: Cheapest is start on cost[1], pay that cost and go to the top.

Example 2:

Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
Explanation: Cheapest is start on cost[0], and only step on 1s, skipping cost[3].

Note:

1. cost will have a length in the range [2, 1000].
2. Every cost[i] will be an integer in the range [0, 999].

最近在刷动态规划的题，这篇文章是我写的动态规划一点想法，和大家分享一下

1. Dp

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        dp = [0] * (len(cost)+1)
        for i in range(2, len(dp)):
            dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
        return dp[-1]

从题目中也可以注意到，有些dp的空间是并不需要的，因为我们只需要关注当前位置的前一个(i-1)和前两个(i-2)所以使用两个变量，完全就足够了。

改良版：

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        f1 = 0 # one step behind current position
        f2 = 0 # two steps behind current postion
        for i in range(2, len(cost)+1):
            f2, f1 = f1, min(f1 + cost[i-1], f2 + cost[i-2])
        return f1

⚠️注意：

1. 由于题目给的note明确说明cost长度大于等于2，所以不用考虑edge case。
2. 对题目的理解是否准确，并不是跳到cost的最后就结束了(not range(2, len(cost)))，而是要跳出cost (range(2, len(cost)+1))